package org.algorithm.Sort;

public class HeapSort2 {


    private void sort(int[] arr) {

        //1、生成大顶堆
        buildHeap(arr);

        //2、对大顶堆的数组开始排序，将大顶堆最大值（第一个数）与数组的最后一个数进行交换，对剩下数组重新构建，使其满足大顶堆

        for (int i = arr.length - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i);
        }

    }


    private void heapify(int[] array, int i) {
        int n = array.length;

        int left = 2 * i + 1;
        int right = 2 * i + 2;

        int max = i;

        if (left < n && array[left] > array[max]) {
            max = left;
        }

        if (right < n && array[right] > array[max]) {
            max = right;
        }

        if (max != i) {
            int temp = array[max];
            array[max] = array[i];
            array[i] = temp;

            heapify(array, max);
        }

    }

    //大顶堆的构建
    public void buildHeap(int[] array) {
        int n = array.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, i);
        }
    }

    public static void main(String[] args) {
        HeapSort2 heapSort2 = new HeapSort2();
        int arr[] = {31, 21, 63, 555, 2, 4};
        heapSort2.sort(arr);

        printArray(arr);
    }


    public static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }


    public void sort2(int[] array) {
        int n = array.length;
        //1、生成大顶堆
        buildHeap2(array);
        //2、对大顶堆的数组开始排序，将大顶堆最大值（第一个数）与数组的最后一个数进行交换，对剩下数组重新构建，使其满足大顶堆
        for (int i = n - 1; i >= 0; i--) {
            int maxTemp = array[0];
            array[0] = array[i];
            array[i] = maxTemp;

            heapify2(array, 0, i);
        }
    }

    public void buildHeap2(int[] array) {
        int n = array.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify2(array, i, n);
        }
    }

    public void heapify2(int[] array, int i, int n) {
        int max = i;
        int left = i * 2 + 1;
        int right = i * 2 + 2;

        if (left < n && array[max] < array[left]) {
            max = left;
        }

        if (right < n && array[max] < array[right]) {
            max = right;
        }

        if (max != i) {
            int temp = array[i];
            array[i] = array[max];
            array[max] = temp;
            //对修改后的节点再进行一次堆化
            heapify2(array, max, n);
        }
    }


}
